/*      > C.RegEx - Extended regular expression matching and search     */

/* Extended regular expression matching and search.
   Copyright (C) 1985 Free Software Foundation, Inc.

                       NO WARRANTY

  BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
CORRECTION.

 IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.

                GENERAL PUBLIC LICENSE TO COPY

  1. You may copy and distribute verbatim copies of this source file
as you receive it, in any medium, provided that you conspicuously and
appropriately publish on each copy a valid copyright notice "Copyright
(C) 1985 Free Software Foundation, Inc."; and include following the
copyright notice a verbatim copy of the above disclaimer of warranty
and of this License.  You may charge a distribution fee for the
physical act of transferring a copy.

  2. You may modify your copy or copies of this source file or
any portion of it, and copy and distribute such modifications under
the terms of Paragraph 1 above, provided that you also do the following:

    a) cause the modified files to carry prominent notices stating
    that you changed the files and the date of any change; and

    b) cause the whole of any work that you distribute or publish,
    that in whole or in part contains or is a derivative of this
    program or any part thereof, to be licensed at no charge to all
    third parties on terms identical to those contained in this
    License Agreement (except that you may choose to grant more extensive
    warranty protection to some or all third parties, at your option).

    c) You may charge a distribution fee for the physical act of
    transferring a copy, and you may at your option offer warranty
    protection in exchange for a fee.

Mere aggregation of another unrelated program with this program (or its
derivative) on a volume of a storage or distribution medium does not bring
the other program under the scope of these terms.

  3. You may copy and distribute this program (or a portion or derivative
of it, under Paragraph 2) in object code or executable form under the terms
of Paragraphs 1 and 2 above provided that you also do one of the following:

    a) accompany it with the complete corresponding machine-readable
    source code, which must be distributed under the terms of
    Paragraphs 1 and 2 above; or,

    b) accompany it with a written offer, valid for at least three
    years, to give any third party free (except for a nominal
    shipping charge) a complete machine-readable copy of the
    corresponding source code, to be distributed under the terms of
    Paragraphs 1 and 2 above; or,

    c) accompany it with the information you received as to where the
    corresponding source code may be obtained.  (This alternative is
    allowed only for noncommercial distribution and only if you
    received the program in object code or executable form alone.)

For an executable file, complete source code means all the source code for
all modules it contains; but, as a special exception, it need not include
source code for modules which are standard libraries that accompany the
operating system on which the executable file runs.

  4. You may not copy, sublicense, distribute or transfer this program
except as expressly provided under this License Agreement.  Any attempt
otherwise to copy, sublicense, distribute or transfer this program is void and
your rights to use the program under this License agreement shall be
automatically terminated.  However, parties who have received computer
software programs from you with this License Agreement will not have
their licenses terminated so long as such parties remain in full compliance.

  5. If you wish to incorporate parts of this program into other free
programs whose distribution conditions are different, write to the Free
Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
worked out a simple rule that can be stated here, but we will often permit
this.  We will be guided by the two goals of preserving the free status of
all derivatives of our free software and of promoting the sharing and reuse of
software.


In other words, you are welcome to use, share and improve this program.
You are forbidden to forbid anyone else to use, share and improve
what you give them.   Help stamp out software-hoarding!  */


/* To test, compile with -Dtest.
   This testable feature turns this into a self-contained program
   which reads a pattern, describes how it compiles, then reads a
   string and searches for it.
*/

/* To debug, compile with -Ddebug or -Dmatch.
   This switches on progress tracing at various levels.
   -Ddebug reports all attempted string (anchored) matches.
   -Dmatch reports all attempted character matches.

   -Dmatch includes -Ddebug reporting.
 */

#if !defined(debug) && !defined(match)

#define D0(x)   (void)0
#define D1(x)   (void)0

#else

#define D0(x)   (x)

#ifdef match
#define D1(x)   (x)
#else
#define D1(x)   (void)0
#endif

#endif

/*
 * Define the syntax stuff, so we can do the \<...\> things.
 */

#ifndef Sword /* must be non-zero in some of the tests below... */
#define Sword 1
#endif

#ifdef SYNTAX_TABLE

char *re_syntax_table;

#else

static char re_syntax_table[256];

#endif /* SYNTAX_TABLE */

#include <limits.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <ctype.h>
#include <stdio.h>

#include "Regex.H"
#include "Defns.H"
#include "Chars.H"

/***** Internal routines *****/

#ifndef SYNTAX_TABLE

static void init_syntax_once (void)
{
        register int c;
        static int done = 0;

        if (done)
                return;

        memset(re_syntax_table, 0, sizeof(re_syntax_table));

        for (c = 'a'; c <= 'z'; c++)
                re_syntax_table[c] = Sword;

        for (c = 'A'; c <= 'Z'; c++)
                re_syntax_table[c] = Sword;

        for (c = '0'; c <= '9'; c++)
                re_syntax_table[c] = Sword;

        done = 1;
}

#endif

/* Store where `from' points a jump operation to jump to where `to' points.
  `opcode' is the opcode to store.
*/

static void store_jump (char *from, char opcode, char *to)
{
        from[0] = opcode;
        from[1] = (to - (from + JUMP_LEN)) & 0377;
        from[2] = (to - (from + JUMP_LEN)) >> 8;
}

/* Open up space at char FROM, and insert there a jump to TO.
   CURRENT_END gives te end of the storage no in use,
   so we know how much data to copy up.
   OP is the opcode of the jump to insert.

   If you call this function, you must zero out pending_exact.  */

static void insert_jump (char *from, char op, char *to, char *current_end)
{
        register char *pto = current_end + JUMP_LEN;
        register char *pfrom = current_end;

        while ( pfrom != from )
                *--pto = *--pfrom;

        store_jump (from, op, to);
}

/* Given a pattern, compute a fastmap from it.
   The fastmap records which of the possible characters can start a string
   that matches the pattern. This fastmap is used by re_search to skip
   quickly over totally implausible text.

   The components of re describe the pattern to be used.
*/

static void re_compile_fastmap (REGEX *re)
{
        unsigned char *pattern = (unsigned char *) re->buffer;
        int size = re->used;
        register char *fastmap = re->fastmap;
        register unsigned char *p = pattern;
        register unsigned char *pend = pattern + size;
        register int i, j;
        unsigned char *translate = (unsigned char *) re->translate;

        unsigned char *stackb[MAX_FAILURES];
        unsigned char **stackp = stackb;

        memset(fastmap,0,BITMAP_LEN);

        re->fastmap_ok  = 1;
        re->can_be_null = 0;

        for ( ; ; )
        {
                if ( p == pend )
                {
                        re->can_be_null = 1;
                        break;
                }

                switch ( *p )
                {
                /* ----- 0-character RE's ----- */

                case startline:
                case startbuf:
                case endbuf:
                case startword:
                case endword:
                case wordbound:
                case NOT(startline):
                case NOT(endline):
                case NOT(startbuf):
                case NOT(endbuf):
                case NOT(startword):
                case NOT(endword):
                case NOT(wordbound):
                        ++p;
                        continue;

                case endline:
                        SETBIT(fastmap,TRANSLATE('\n'));

                        if ( re->can_be_null != 1 )
                                re->can_be_null = 2;

                        ++p;
                        continue;

                /* ----- 1-character RE's ----- */

                case anychar:
                        for ( i = 0; i <= UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( j != '\n' )
                                        SETBIT(fastmap,j);
                        }
                        ++p;
                        break;

                case NOT(anychar):
                        ++p;
                        break;

                case wordchar:
                        for ( i = 0; i < UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( SYNTAX(j) == Sword )
                                        SETBIT(fastmap,j);
                        }
                        ++p;
                        break;

                case NOT(wordchar):
                        for ( i = 0; i < UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( SYNTAX(j) != Sword )
                                        SETBIT(fastmap,j);
                        }
                        ++p;
                        break;

                case notchar:
                        for ( i = 0; i < UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( j != p[1] )
                                        SETBIT(fastmap,j);
                        }
                        p += 2;
                        break;

                case charset:
                        for ( i = 0; i < UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( j < p[1]*CHAR_BIT && GETBIT(p+2,j) )
                                        SETBIT(fastmap,j);
                        }
                        p += 2 + p[1];
                        break;

                case NOT(charset):
                        for ( i = 0; i < UCHAR_MAX; ++i )
                        {
                                j = TRANSLATE(i);
                                if ( j >= p[1]*CHAR_BIT || !GETBIT(p+2,j) )
                                        SETBIT(fastmap,j);
                        }
                        p += 2 + p[1];
                        break;

                /* ----- multi-character RE's ----- */

                case duplicate:
                        re->can_be_null = 1;
                        SETBIT(fastmap,TRANSLATE('\n'));
                        p += 2;
                        break;

                case exactn:
                        if ( p[1] != 0 )
                                SETBIT(fastmap,p[2]);

                        p += 2 + p[1];
                        break;

                /* ----- RE operators: jumps ----- */

                case jump:
                case finalise_jump:
                case maybe_finalise_jump:
                case dummy_failure_jump:
                        re->can_be_null = 1;

                        /* Follow the jump to its destination */
                        i = JUMP_DEST(p+1);
                        p += JUMP_LEN + i;

                        /* Further processing only required if we have just
                           jumped backwards to an on_failure_jump
                         */

                        if ( i > 0 )
                                continue;

                        if ( *p != on_failure_jump )
                                continue;

                        /* Follow the on_failure_jump to its destination.
                           As we have jumped backwards to it, we can assume
                           that we have already processed the non-failure
                           case. Note that this assumption is only valid
                           because of the structure of the pattern re_compile
                           sets up. As an example of a general pattern which
                           will not work, consider
                              1. Jump to (4)
                              2. Failure jump to (5)
                              3. Literal "abc"
                              4. Jump to (2)
                              5. Literal "def"
                           where, because we first reach (2) via a backward
                           jump from (4), the case (3) is never considered.
                           This should probably be fixed, but it is not urgent
                           unless re_compile is changed.

                           If the destination of the failure jump is already
                           stacked, we can unstack it as we are now doing it.
                         */

                        i = JUMP_DEST(p+1);
                        p += JUMP_LEN + i;

                        if ( stackp != stackb && *stackp == p )
                                --stackp;

                        continue;

                case on_failure_jump:
                        i = JUMP_DEST(p+1);
                        p += JUMP_LEN;

                        /* stack the destination for later checking */
                        *++stackp = p + i;

                        continue;

                /* ----- RE operators: memory ----- */

                case start_memory:
                case stop_memory:
                        p += 2;
                        continue;

                }

                /* If we get here, we have successfully found the possible
                   starting characters of one path of the pattern.
                   We need not follow this path any farther. Instead,
                   look at the next alternative remembered in the stack.
                 */

                if (stackp != stackb)
                        p = *stackp--;
                else
                        break;
        }
}

static void resolve_jumps (REGEX *re)
{
        register char *p = re->buffer;
        char *end = p + re->used;
        char *dest;
        char *jump_instr;
        int i;
        int in_set;
        unsigned char ch;

        while ( p != end )
        {
                switch ( *p )
                {

                /* ----- 1-byte operations ----- */

                case startline:
                case endline:
                case startbuf:
                case endbuf:
                case startword:
                case endword:
                case wordbound:
                case anychar:
                case wordchar:
                case NOT(startline):
                case NOT(endline):
                case NOT(startbuf):
                case NOT(endbuf):
                case NOT(startword):
                case NOT(endword):
                case NOT(wordbound):
                case NOT(anychar):
                case NOT(wordchar):
                        ++p;
                        break;

                /* ----- 2-byte operations ----- */

                case notchar:
                case duplicate:
                case start_memory:
                case stop_memory:
                        p += 2;
                        break;

                /* ----- operations followed by a count byte ----- */

                case charset:
                case NOT(charset):
                case exactn:
                        p += 2 + p[1];
                        break;

                /* ----- jump operations ----- */

                case jump:
                case on_failure_jump:
                case finalise_jump:
                case dummy_failure_jump:
                        p += JUMP_LEN;
                        break;

                /* ----- possibly finalise this jump ----- */

                case maybe_finalise_jump:
                        jump_instr = p;
                        p += JUMP_LEN;

                        /* if nothing to follow, finalise */
                        if ( p == end )
                        {
                                *jump_instr = finalise_jump;
                                break;
                        }

                        /* if no definite character following, jump always */
                        if ( !(*p == exactn && p[1] != 0) && *p != endline )
                        {
                                *jump_instr = jump;
                                break;
                        }

                        i = JUMP_DEST(jump_instr+1);
                        dest = p + i;

                        /* if not a jump to a failure point, jump always */
                        if ( *dest != on_failure_jump )
                        {
                                *jump_instr = jump;
                                break;
                        }

                        /* get the character to follow the maybe_finalise */
                        ch = ( *p == endline ? '\n' : p[2] );

                        /* skip the on_failure_jump */
                        dest += JUMP_LEN;

                        if ( *dest == exactn )
                        {
                                if ( dest[1] != 0 && dest[2] != ch )
                                        *jump_instr = finalise_jump;
                                else
                                        *jump_instr = jump;

                                break;
                        }

                        else if ( *dest == charset || *dest == NOT(charset) )
                        {
                                in_set = ( ch < dest[1]*CHAR_BIT && GETBIT(dest+2,ch) );
                                if
                                (
                                        ( in_set && ( *dest & NOT_BIT ) )
                                ||
                                        ( !in_set && !( *dest & NOT_BIT ) )
                                )
                                        *jump_instr = finalise_jump;
                                else
                                        *jump_instr = jump;

                                break;
                        }

                        else
                        {
                                *jump_instr = jump;
                                break;
                        }
                }
        }
}

/***** External routines *****/

/* Create an initially empty regular expression buffer.
   The user can specify a buffer (and its size). Leaving this as zero
   results in re_compile setting up its own buffers.
   A translation table can also be specified.
*/

REGEX *re_create (const char *buffer, int len, const char *translate)
{
        REGEX *re;

        re = malloc(sizeof(*re));

        re->buffer      = (char *)buffer;       /* User-supplied buffer */
        re->allocated   = len;                  /* Current length of buffer */
        re->used        = 0;                    /* None used yet */
        re->realloc_ok  = 0;                    /* Buffer not from malloc() */
        re->translate   = translate;            /* User-supplied trans table */
        re->fastmap     = malloc(BITMAP_LEN);   /* Fastmap from malloc() */
        re->fastmap_ok  = 0;                    /* Not set up yet... */
        re->can_be_null = 0;                    /* Not yet... */

        return re;
}

/* Delete a regular expression buffer.
   Any memory allocated by the system for the regular expression buffer
   will automatically be freed. User-supplied space (ie. the translation
   table and/or a user-supplied buffer) must be cleared by the user
   before calling re_free.
 */

void re_free (REGEX *re)
{
        /* Was the buffer obtained from malloc() */

        if ( re->realloc_ok )
                free(re->buffer);

        free(re->fastmap);

        free(re);
}

/* re_compile takes a regular-expression string and converts it
   into a buffer full of byte commands for matching.

   PATTERN      is the pattern string.
   RE           is a (REGEX *) which points to the information on where to
                store the byte commands.
                This structure contains a (char *) which points to the
                actual space. This may be null, in which case re_compile will
                allocate space of its own (using malloc).

   The number of bytes of commands can be found out by looking in RE,
   after re_compile returns.
*/

char *re_compile (const char *pattern, REGEX *re)
{
        register char *b = re->buffer;
        register const char *p = pattern;
        register unsigned c;
        unsigned char *translate = (unsigned char *)re->translate;

        unsigned c1;

        int zero_times_ok;
        int many_times_ok;


/* Various syntax processing variables - all addresses are offsets from
   re->buffer, or -1 to indicate "not set"
 */

        int alt_start;          /* start address of last alternative */
        int rep_start;          /* start address of last repeatable value */
        int pending_alt;        /* address of jump at start of current alternative */
        int pending_exact;      /* address of count byte of last exact construct */

        int pending_not;        /* number of outstanding nots */

/* Stack of information saved and restored by brackets.
   Four stack elements are pushed by each bracket:
      First, the value of OFFSET(b) (for later use as rep_start).
      Second, the value of pending_alt.
      Third, the value of regnum (or zero if this is not a marked bracket).
      Fourth, the value of alt_start.
*/

        int stackb[STACK_SIZE * 4];
        int *stackp = stackb;
        int *stacke = stackb + (STACK_SIZE * 4);

/* Counts OPEN_MARKED_BRACKET's as they are encountered.
   Remembered for the matching CLOSE_MARKED_BRACKET, where it becomes
   the "register number" to put in the stop_memory command.
*/

        int regnum = 1;

#ifndef SYNTAX_TABLE
        /*
         *  Initialize the syntax table.
         */

        init_syntax_once();
#endif

        re->fastmap_ok = 0;

        if ( re->allocated == 0 )
        {
                re->allocated = ALLOC_INCR;
                re->buffer = malloc (ALLOC_INCR);
                if ( !re->buffer )
                        goto memory_exhausted;
                re->realloc_ok = 1;
                b = re->buffer;
        }

        alt_start = OFFSET(b);
        rep_start = NONE;

        pending_alt = NONE;
        pending_exact = NONE;
        pending_not = 0;

        while ( *p )
        {
                if ( (b - re->buffer) > (re->allocated - MAX_ADD) )
                {
                        ptrdiff_t diff = b - re->buffer;

                        if ( ! re->realloc_ok )
                                goto buffer_overflow;

                        re->allocated += ALLOC_INCR;
                        re->buffer = realloc(re->buffer,re->allocated);

                        if ( !re->buffer )
                                goto memory_exhausted;

                        b = re->buffer + diff;
                }

                PATFETCH(c);

                switch (c)
                {
                /* ----- 0-character RE's ----- */

                case START_LINE:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(startline));
                        else
                                PATPUSH(startline);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case END_LINE:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(endline));
                        else
                                PATPUSH(endline);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case START_BUF:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(startbuf));
                        else
                                PATPUSH(startbuf);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case END_BUF:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(endbuf));
                        else
                                PATPUSH(endbuf);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case START_WORD:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(startword));
                        else
                                PATPUSH(startword);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case END_WORD:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(endword));
                        else
                                PATPUSH(endword);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case WORD_BOUND:
                        rep_start = NONE;

                        if ( pending_not & 1 )
                                PATPUSH(NOT(wordbound));
                        else
                                PATPUSH(wordbound);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                /* ----- 1-character RE's ----- */

                case ANY_CHAR:
                        rep_start = OFFSET(b);

                        if ( pending_not & 1 )
                                PATPUSH(NOT(anychar));
                        else
                                PATPUSH(anychar);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case WORD_CHAR:
                        rep_start = OFFSET(b);

                        if ( pending_not & 1 )
                                PATPUSH(NOT(wordchar));
                        else
                                PATPUSH(wordchar);

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                case START_SET:
                        rep_start = OFFSET(b);

                        if ( pending_not & 1 )
                                PATPUSH(NOT(charset));
                        else
                                PATPUSH(charset);

                        PATPUSH(BITMAP_LEN);

                        memset(b,0,BITMAP_LEN);

                        for ( ; ; )
                        {
                                PATFETCH(c);
                                if ( c == ']' )
                                        break;

                                if ( IS_BACKSLASH(c) )
                                {
                                        switch ( c )
                                        {
                                        case BACKSLASH('b'):
                                                c = '\b';
                                                break;

                                        case BACKSLASH('f'):
                                                c = '\f';
                                                break;

                                        case BACKSLASH('n'):
                                                c = '\n';
                                                break;

                                        case BACKSLASH('r'):
                                                c = '\r';
                                                break;

                                        case BACKSLASH('t'):
                                                c = '\t';
                                                break;

                                        case BACKSLASH('v'):
                                                c = '\v';
                                                break;

                                        default:
                                                c = LITERAL(c);
                                                break;
                                        }
                                }

                                if ( *p == '-' && p[1] != ']' )
                                {
                                        ++p;    /* skip the '-' */

                                        PATFETCH(c1);

                                        if ( IS_BACKSLASH(c1) )
                                        {
                                                switch ( c1 )
                                                {
                                                case BACKSLASH('b'):
                                                        c1 = '\b';
                                                        break;

                                                case BACKSLASH('f'):
                                                        c1 = '\f';
                                                        break;

                                                case BACKSLASH('n'):
                                                        c1 = '\n';
                                                        break;

                                                case BACKSLASH('r'):
                                                        c1 = '\r';
                                                        break;

                                                case BACKSLASH('t'):
                                                        c1 = '\t';
                                                        break;

                                                case BACKSLASH('v'):
                                                        c1 = '\v';
                                                        break;

                                                default:
                                                        c1 = LITERAL(c1);
                                                        break;
                                                }
                                        }

                                        while ( c <= c1 )
                                        {
                                                SETBIT(b,c);
                                                ++c;
                                        }
                                }
                                else
                                {
                                        SETBIT(b,c);
                                }
                        }

                        while ( ( b[-1] > 0 ) && ( b[ b[-1] - 1 ] == 0 ) )
                                --b[-1];

                        b += b[-1];

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                /* ----- multi-character RE's ----- */

                case MEMORY(1):
                case MEMORY(2):
                case MEMORY(3):
                case MEMORY(4):
                case MEMORY(5):
                case MEMORY(6):
                case MEMORY(7):
                case MEMORY(8):
                case MEMORY(9):
                        if ( pending_not )
                                goto invalid_not;

                        rep_start = OFFSET(b);

                        PATPUSH(duplicate);
                        PATPUSH(MEMNO(c));

                        pending_not = 0;
                        pending_exact = NONE;

                        break;

                /* ----- RE operators ----- */

                case NOT_OP:
                        ++pending_not;

                        break;

                case ALT:
                        if ( pending_not )
                                goto invalid_not;

                        insert_jump(ADDR(alt_start),on_failure_jump,b+2*JUMP_LEN,b);
                        b += JUMP_LEN;

                        if ( pending_alt != NONE )
                                store_jump(ADDR(pending_alt),jump,b);

                        pending_alt = OFFSET(b);
                        b += JUMP_LEN;

                        pending_exact = NONE;
                        rep_start = NONE;
                        alt_start = OFFSET(b);

                        break;

                case REPEAT_0_PLUS:
                case REPEAT_1_PLUS:
                case OPTIONAL:
                        if ( pending_not )
#ifdef CONTEXT_INDEPENDENT_OPS
                                goto invalid_not;
#else
                        {
                                --pending_not;
                                PATUNFETCH(c);
                                c = NOT_OP;
                                goto normal_char;
                        }
#endif

                        if ( rep_start == NONE )
#ifdef CONTEXT_INDEPENDENT_OPS
                                goto invalid_pattern;
#else
                                goto normal_char;
#endif

                        zero_times_ok = 0;
                        many_times_ok = 0;

                        for ( ; ; )
                        {
                                zero_times_ok |= ( c != REPEAT_1_PLUS );
                                many_times_ok |= ( c != OPTIONAL );

                                if ( *p == '\0' )
                                        break;

                                PATFETCH(c);

                                if
                                (
                                        c != REPEAT_0_PLUS
                                &&
                                        c != REPEAT_1_PLUS
                                &&
                                        c != OPTIONAL
                                )
                                {
                                        PATUNFETCH(c);
                                        break;
                                }
                        }

                        if ( many_times_ok )
                        {
                                store_jump(b, maybe_finalise_jump, ADDR(rep_start) - JUMP_LEN);
                                b += JUMP_LEN;
                        }

                        insert_jump(ADDR(rep_start), on_failure_jump, b + JUMP_LEN, b);
                        b += JUMP_LEN;

                        if ( !zero_times_ok )
                        {
                                insert_jump(ADDR(rep_start), dummy_failure_jump, ADDR(rep_start) + JUMP_LEN*2, b);
                                b += JUMP_LEN;
                        }

                        pending_exact = NONE;
                        pending_not = 0;
                        rep_start = NONE;

                        break;

                /* ----- Brackets ----- */

                case OPEN_BRACKET:
                case OPEN_MARKED_BRACKET:
                        if ( pending_not )
                                goto invalid_not;

                        if ( stackp >= stacke )
                                goto nesting_too_deep;

                        if ( c == OPEN_MARKED_BRACKET )
                        {
                                if ( regnum < RE_MAX_REGS )
                                {
                                        PATPUSH(start_memory);
                                        PATPUSH(regnum);
                                }
                        }

                        *stackp++ = OFFSET(b);
                        *stackp++ = pending_alt;
                        *stackp++ = ( c == OPEN_MARKED_BRACKET ? regnum++ : 0 );
                        *stackp++ = alt_start;

                        alt_start = OFFSET(b);
                        rep_start = NONE;
                        pending_alt = NONE;
                        pending_exact = NONE;

                        break;

                case CLOSE_BRACKET:
                case CLOSE_MARKED_BRACKET:
                        if ( pending_not )
                                goto invalid_not;

                        if ( stackp <= stackb )
                                goto unmatched_close;

                        if ( pending_alt != NONE )
                                store_jump(ADDR(pending_alt),jump,b);

                        alt_start = *--stackp;

                        if ( *--stackp )
                        {
                                if ( c != CLOSE_MARKED_BRACKET )
                                        goto unmatched_close;

                                PATPUSH(stop_memory);
                                PATPUSH(*stackp);
                        }

                        pending_alt = *--stackp;
                        rep_start = *--stackp;

                        pending_exact = NONE;

                        break;

                /* ----- Normal characters ----- */

                case BACKSLASH('b'):
                        c = '\b';
                        goto normal_char;

                case BACKSLASH('f'):
                        c = '\f';
                        goto normal_char;

                case BACKSLASH('n'):
                        c = '\n';
                        goto normal_char;

                case BACKSLASH('r'):
                        c = '\r';
                        goto normal_char;

                case BACKSLASH('t'):
                        c = '\t';
                        goto normal_char;

                case BACKSLASH('v'):
                        c = '\v';
                        goto normal_char;

                default:
                normal_char:

                        if ( IS_BACKSLASH(c) )
                                c = TRANSLATE(LITERAL(c));

                        if
                        (
                                pending_exact == NONE
                        ||
                                *ADDR(pending_exact) == UCHAR_MAX
                        ||
                                POSTFIX_OP(p)
                        ||
                                ( pending_not & 1 )
                        )
                        {
                                if ( pending_not & 1 )
                                {
                                        rep_start = OFFSET(b);

                                        PATPUSH(notchar);
                                        PATPUSH(c);

                                        pending_not = 0;
                                        pending_exact = NONE;

                                        break;
                                }
                                else
                                {
                                        rep_start = OFFSET(b);

                                        PATPUSH(exactn);
                                        pending_exact = OFFSET(b);

                                        PATPUSH(0);
                                }
                        }

                        PATPUSH(c);
                        (*ADDR(pending_exact))++;

                        break;
                }
        }

        if ( pending_alt != NONE )
                store_jump (ADDR(pending_alt),jump,b);

        if ( pending_not )
        {
#ifdef CONTEXT_INDEPENDENT_OPS
                goto invalid_not;
#else
                --pending_not;
                c = NOT_OP;
                goto normal_char;
#endif
        }

        if ( stackp != stackb )
                goto unmatched_open;

        re->used = b - re->buffer;

        /* if possible, free unused space in buffer */
        if ( re->realloc_ok )
        {
                re->allocated = re->used;
                re->buffer = realloc(re->buffer,re->used);
        }

        re_compile_fastmap(re);

        resolve_jumps(re);

        return 0;

#ifdef CONTEXT_INDEPENDENT_OPS
invalid_pattern:
        return "Invalid regular expression";
#endif

invalid_not:
        return "Not operator can only apply to a 0-char or 1-char RE";

buffer_overflow:
        return "Not enough space in supplied buffer";

unmatched_open:
        return "Unmatched opening bracket";

unmatched_close:
        return "Unmatched closing bracket";

end_of_pattern:
        return "Premature end of regular expression";

nesting_too_deep:
        return "Nesting too deep";

memory_exhausted:
        return "Memory exhausted";
}

int re_anchored_match (const REGEX *re, const char *str, int len, int pos, REGMEM *mem)
{
        register const char *p = re->buffer;
        register const char *d = str + pos;
        const char *end = str + ( len == -1 ? strlen(str) : len );
        const char *patt_end = re->buffer + re->used;
        register const char *translate = re->translate;
        int i;
        int n;
        char ch;
        char *q;
        int ok;
        REGMEM memory;

        const char **stack = malloc(FAIL_STACK_INCR);
        int stackp = 0;
        int stacke = FAIL_STACK_INCR;

        D0(fprintf(stderr, "Anchored match vs. `%.*s' at pos %d\n",len,str,pos));

        if ( mem == NULL )
                mem = &memory;

        for ( i = 0; i < RE_MAX_REGS; ++i )
        {
                mem->start[i] = NULL;
                mem->len[i] = 0;
        }

        for ( ; ; )
        {
                if ( d > end )
                {
                        /* Off the end of the string - must fail */

                        goto fail;
                }

                if ( p == patt_end )
                {
                        /* At end of pattern - we have succeeded in matching */

                        mem->start[0] = (char *)str + pos;
                        mem->len[0] = d - str - pos;

                        D0(fprintf(stderr,"Success - return %d\n",d-str-pos));
                        return (d - str - pos);
                }

                switch ( *p )
                {

                /* ----- 0-character RE's ----- */

                case startline:
                case NOT(startline):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sstartline match\n", ok ? "NOT " : "" ));

                        if ( d == str || d[-1] == '\n' )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case endline:
                case NOT(endline):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sendline match\n", ok ? "NOT " : "" ));

                        if ( d == end || d[0] == '\n' )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case startbuf:
                case NOT(startbuf):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sstartbuf match\n", ok ? "NOT " : "" ));

                        if ( d == str )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case endbuf:
                case NOT(endbuf):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sendbuf match\n", ok ? "NOT " : "" ));

                        if ( d == end )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case startword:
                case NOT(startword):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sstartword match\n", ok ? "NOT " : "" ));

                        if
                        (
                                d == str                        /* at start */
                        ||
                                (
                                        d != end                /* not at end */
                                &&
                                        SYNTAX(d[0]) == Sword   /* this is a letter */
                                &&
                                        SYNTAX(d[-1]) != Sword  /* prev is not */
                                )
                        )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case endword:
                case NOT(endword):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sendword match\n", ok ? "NOT " : "" ));

                        if
                        (
                                d == end                        /* at end */
                        ||
                                (
                                        d != str                /* not at start */
                                &&
                                        SYNTAX(d[-1]) == Sword  /* prev is a letter */
                                &&
                                        SYNTAX(d[0]) != Sword   /* this is not */
                                )
                        )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case wordbound:
                case NOT(wordbound):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %swordbound match\n", ok ? "NOT " : "" ));

                        if
                        (
                                d == str
                        ||
                                d == end
                        ||
                                ( SYNTAX(d[-1]) == Sword ) != ( SYNTAX(d[0]) == Sword )
                        )
                                ok = !ok;

                        if ( ok )
                                break;
                        else
                                goto fail;

                /* ----- 1-character RE's ----- */

                case anychar:
                case NOT(anychar):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %sanychar match vs. `%c' (%d)\n",
                           ok ? "NOT " : "", TRANSLATE(*d), TRANSLATE(*d) ));

                        if ( d == end )
                                goto fail;

                        if ( TRANSLATE(*d) != '\n' )
                                ok = !ok;

                        ++d;

                        if ( ok )
                                break;
                        else
                                goto fail;

                case wordchar:
                case NOT(wordchar):

                        ok = IS_NOT(*p);
                        ++p;

                        D1(fprintf(stderr,
                           "Trying %swordchar match\n", ok ? "NOT " : "" ));

                        if ( d == end )
                                goto fail;

                        if ( SYNTAX(TRANSLATE(*d)) == Sword )
                                ok = !ok;

                        ++d;

                        if ( ok )
                                break;
                        else
                                goto fail;
                case notchar:

                        D1(fprintf(stderr, "Trying not %c match\n", p[1] ));

                        if ( d == end )
                        {
                                p += 2;
                                goto fail;
                        }

                        if ( TRANSLATE(*d) != p[1] )
                        {
                                p += 2;
                                ++d;
                                break;
                        }

                        goto fail;

                case charset:
                case NOT(charset):

                        ok = IS_NOT(*p);

                        D1(fprintf(stderr,
                           "Trying %scharset match\n", ok ? "NOT " : "" ));

                        if ( d == end )
                        {
                                p += 2 + p[1];
                                goto fail;
                        }

                        ch = TRANSLATE(*d);

                        if ( ch < p[1]*CHAR_BIT && GETBIT(p+2,ch) )
                                ok = !ok;

                        p += 2 + p[1];
                        ++d;

                        if ( ok )
                                break;
                        else
                                goto fail;

                /* ----- multi-character RE's ----- */

                case exactn:

                        ++p;

                        D1(fprintf(stderr,
                           "Trying exact %.*s match\n", p[0], &p[1] ));

                        if ( end - d < *p )
                        {
                                p += *p + 1;
                                goto fail;
                        }

                        for ( i = *p++; i > 0; --i )
                        {
                                if ( TRANSLATE(*d) != *p++ )
                                        goto fail;
                                ++d;
                        }

                        break;

                case duplicate:

                        ++p;

                        n = *p++;
                        q = mem->start[n];

                        D1(fprintf(stderr,
                           "Trying mem %d (%.*s) match\n", n, mem->len[n], q));

                        if ( end - d < mem->len[n] )
                                goto fail;

                        for ( i = mem->len[n]; i > 0; --i )
                        {
                                if ( TRANSLATE(*d) != TRANSLATE(*q) )
                                        goto fail;
                                ++d;
                                ++q;
                        }

                        break;

                /* ----- RE operators: jumps ----- */

                case jump:
                case maybe_finalise_jump: /* this should have been resolved */

                normal_jump:

                        p += JUMP_LEN + JUMP_DEST(p+1);
                        break;

                case on_failure_jump:

                        if ( stackp == stacke )
                        {
                                /* Extend the failure stack */

                                stack = realloc(stack,(stacke+FAIL_STACK_INCR)*sizeof(const char *));
                                stacke += FAIL_STACK_INCR;

                                if ( !stack )   /* out of memory */
                                        return RE_ERROR;
                        }

                        i = JUMP_DEST(p+1);
                        p += JUMP_LEN;

                        stack[stackp++] = p + i;
                        stack[stackp++] = d;

                        break;

                case finalise_jump:

                        stackp -= 2;

                        goto normal_jump;

                case dummy_failure_jump:

                        if ( stackp == stacke )
                        {
                                /* Extend the failure stack */

                                stack = realloc(stack,(stacke+FAIL_STACK_INCR)*sizeof(const char *));
                                stacke += FAIL_STACK_INCR;

                                if ( !stack )   /* out of memory */
                                        return RE_ERROR;
                        }

                        stack[stackp++] = NULL;
                        stack[stackp++] = NULL;

                        goto normal_jump;

                /* ----- RE operators: memory ----- */

                case start_memory:

                        mem->start[p[1]] = (char *)d;
                        p += 2;

                        break;

                case stop_memory:

                        mem->len[p[1]] = (char *)d - mem->start[p[1]];
                        p += 2;

                        break;

                }

                /* Successfully matched - check next pattern entry */

                continue;

                /* Failed - pop restart point if any */

        fail:

                if ( stackp == 0 )
                        break;
                else
                {
                        D1(fprintf(stderr, "No good - pop failure points\n"));
                        /* discard dummy failure points */

                        if ( stack[stackp-2] == NULL )
                        {
                                stackp -= 2;
                                goto fail;
                        }

                        d = stack[--stackp];
                        p = stack[--stackp];
                }
        }

        /* If we exit the match loop, we have failed to match */

        D0(fprintf(stderr,"Failure - return %d\n",RE_FAIL));
        return RE_FAIL;
}

int re_match (const REGEX *re, const char *str, int len, REGMEM *mem)
{
        register const char *fastmap = re->fastmap;
        register const char *translate = re->translate;
        int i = 0;

        if ( len == -1 )
                len = strlen(str);

        /* If the match is anchored, call re_anchored_match directly */

        if ( re->used > 0 && re->buffer[0] == startbuf )
        {
                if ( re_anchored_match(re,str,len,0,mem) >= 0 )
                        return 0;
                else
                        return RE_FAIL;
        }


        /* Match at each possible position through the string */

        while ( i < len )
        {

                /* If the pattern cannot match an initial null string,
                   skip over all characters not in the fastmap
                 */

                if ( re->can_be_null != 1 )
                {
                        while ( i < len && !GETBIT(fastmap,TRANSLATE(str[i])) )
                        {
                                ++i;
                        }
                }

                /* If we have reached the end, and the pattern cannot match
                   the final null (only possible if can_be_null is 2),
                   then fail
                 */

                if ( i == len && re->can_be_null == 0 )
                        return RE_FAIL;

                if ( re_anchored_match(re,str,len,i,mem) >= 0 )
                        return i;

                ++i;
        }

        return RE_FAIL;
}

static void printchar (char c)
{
        if ( isprint(c) )
                putchar (c);
        else
        {
                switch (c)
                {
                case '\b':
                        printf("\\b");
                        break;

                case '\f':
                        printf("\\f");
                        break;

                case '\n':
                        printf("\\n");
                        break;

                case '\r':
                        printf("\\r");
                        break;

                case '\t':
                        printf("\\t");
                        break;

                case '\v':
                        printf("\\v");
                        break;

                default:
                        putchar ('\\');
                        putchar (((c >> 6) & 3) + '0');
                        putchar (((c >> 3) & 7) + '0');
                        putchar ((c & 7) + '0');
                }
        }
}

static int printop (char *p, int addr)
{
        int i;
        char c = *p;

        printf("%3d: ",addr);

        /* Set current address for jumps to AFTER the jump */
        addr += JUMP_LEN;

        if ( c & NOT_BIT )
        {
                printf("NOT ");
                c &= ~NOT_BIT;
        }
        switch ( c )
        {
                case startline:
                        printf("{Start line}\n");
                        return 1;

                case endline:
                        printf("{End line}\n");
                        return 1;

                case startbuf:
                        printf("{Start buffer}\n");
                        return 1;

                case endbuf:
                        printf("{End buffer}\n");
                        return 1;

                case startword:
                        printf("{Start word}\n");
                        return 1;

                case endword:
                        printf("{End word}\n");
                        return 1;

                case wordbound:
                        printf("{Word boundary}\n");
                        return 1;

                case anychar:
                        printf("{Any character}\n");
                        return 1;

                case wordchar:
                        printf("{Word character}\n");
                        return 1;

                case notchar:
                        printf("{Not ");
                        printchar(p[1]);
                        printf("}\n");
                        return 2;

                case charset:
                        printf("{Character set [");
                        for ( i = 0; i < UCHAR_MAX; ++i )
                                if ( i < p[1]*CHAR_BIT && GETBIT(p+2,i) )
                                        printchar(i);
                        printf("]}\n");
                        return p[1] + 2;

                case duplicate:
                        printf("{Memory %d}\n",p[1]);
                        return 2;

                case exactn:
                        printf("{Literal ");
                        for ( i = 0; i < p[1]; ++i )
                                printchar(p[2+i]);
                        printf("}\n");
                        return p[1] + 2;

                case jump:
                        printf("{Jump %d}\n",addr+JUMP_DEST(p+1));
                        return JUMP_LEN;

                case on_failure_jump:
                        printf("{Fail %d}\n",addr+JUMP_DEST(p+1));
                        return JUMP_LEN;

                case finalise_jump:
                        printf("{Finalise %d}\n",addr+JUMP_DEST(p+1));
                        return JUMP_LEN;

                case maybe_finalise_jump:
                        printf("{Maybe finalise %d}\n",addr+JUMP_DEST(p+1));
                        return JUMP_LEN;

                case dummy_failure_jump:
                        printf("{Dummy failure %d}\n",addr+JUMP_DEST(p+1));
                        return JUMP_LEN;

                case start_memory:
                        printf("{Start memory %d}\n",p[1]);
                        return 2;

                case stop_memory:
                        printf("{Stop memory %d}\n",p[1]);
                        return 2;

                default:
                        printf("{Unknown ");
                        printchar(p[0]);
                        printf("}\n");
                        return 1;
        }
}

void re_dump (REGEX *buff)
{
        int i;

        printf("\nRegex buffer is :\n-----------------\n\n");

        for (i = 0; i < buff->used; )
                i += printop(&buff->buffer[i],i);

        printf("%3d: {End}\n",i);

        printf("\n%d allocated, %d used.\n", buff->allocated, buff->used);

        if ( buff->fastmap_ok )
        {
                printf("Allowed by fastmap: ");
                for (i = 0; i <= UCHAR_MAX; i++)
                        if ( GETBIT(buff->fastmap,i) )
                                printchar(i);
                printf("\nRE can%s be null %s\n",
                       buff->can_be_null == 0 ? "not" : "",
                       buff->can_be_null == 2 ? "at the end" : "");
        }
}

/*---------------------------------------------------------------------------*/

#ifdef test

#define BUFLEN 255

/* Indexed by a character, gives the upper case equivalent of the character */

static char upcase[0400] =
{
        000,    001,    002,    003,    004,    005,    006,    007,
        010,    011,    012,    013,    014,    015,    016,    017,
        020,    021,    022,    023,    024,    025,    026,    027,
        030,    031,    032,    033,    034,    035,    036,    037,
        040,    041,    042,    043,    044,    045,    046,    047,
        050,    051,    052,    053,    054,    055,    056,    057,
        060,    061,    062,    063,    064,    065,    066,    067,
        070,    071,    072,    073,    074,    075,    076,    077,
        0100,   0101,   0102,   0103,   0104,   0105,   0106,   0107,
        0110,   0111,   0112,   0113,   0114,   0115,   0116,   0117,
        0120,   0121,   0122,   0123,   0124,   0125,   0126,   0127,
        0130,   0131,   0132,   0133,   0134,   0135,   0136,   0137,
        0140,   0101,   0102,   0103,   0104,   0105,   0106,   0107,
        0110,   0111,   0112,   0113,   0114,   0115,   0116,   0117,
        0120,   0121,   0122,   0123,   0124,   0125,   0126,   0127,
        0130,   0131,   0132,   0173,   0174,   0175,   0176,   0177,
        0200,   0201,   0202,   0203,   0204,   0205,   0206,   0207,
        0210,   0211,   0212,   0213,   0214,   0215,   0216,   0217,
        0220,   0221,   0222,   0223,   0224,   0225,   0226,   0227,
        0230,   0231,   0232,   0233,   0234,   0235,   0236,   0237,
        0240,   0241,   0242,   0243,   0244,   0245,   0246,   0247,
        0250,   0251,   0252,   0253,   0254,   0255,   0256,   0257,
        0260,   0261,   0262,   0263,   0264,   0265,   0266,   0267,
        0270,   0271,   0272,   0273,   0274,   0275,   0276,   0277,
        0300,   0301,   0302,   0303,   0304,   0305,   0306,   0307,
        0310,   0311,   0312,   0313,   0314,   0315,   0316,   0317,
        0320,   0321,   0322,   0323,   0324,   0325,   0326,   0327,
        0330,   0331,   0332,   0333,   0334,   0335,   0336,   0337,
        0340,   0341,   0342,   0343,   0344,   0345,   0346,   0347,
        0350,   0351,   0352,   0353,   0354,   0355,   0356,   0357,
        0360,   0361,   0362,   0363,   0364,   0365,   0366,   0367,
        0370,   0371,   0372,   0373,   0374,   0375,   0376,   0377
};

int main (void)
{
        char buf[BUFLEN];
        int i, j;
        char *res;
        char *str;
        REGEX *re[10];
        REGMEM mem;

        for ( i = 0; i < 10; ++i )
                re[i] = re_create(0,0,upcase);

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                i = strlen(buf);
                if ( buf[i-1] == '\n' )
                        buf[i-1] = '\0';

                if ( buf[0] == '\0' )
                        continue;
                else if ( buf[0] == '*' )
                        system(buf);
                else if ( sscanf(buf,"compile %1d %n",&i,&j) == 1 )
                {
                        str = &buf[j];
                        res = re_compile(str,re[i]);
                        if ( res )
                                printf("Error: %s\n",res);
                }
                else if ( sscanf(buf,"display %1d",&i) == 1 )
                        re_dump(re[i]);
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                {
                        for ( j = 0; j < re[i]->used; ++j )
                                printchar(re[i]->buffer[j]);
                        putchar('\n');
                }
                else if ( sscanf(buf,"match %1d %n",&i,&j) == 1 )
                {
                        str = &buf[j];
                        printf("Result = %d\n",re_match(re[i],str,0,&mem));
                }
                else if ( sscanf(buf,"anchored %1d %n",&i,&j) == 1 )
                {
                        str = &buf[j];
                        printf("Result = %d\n",re_anchored_match(re[i],str,0,0,&mem));
                }
                else if ( sscanf(buf,"mem %1d",&i) == 1 )
                {
                        printf("Memory = %.*s\n",mem.len[i],mem.start[i]);
                        printf("Length = %d\n",mem.len[i]);
                }
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        for ( i = 0; i < 10; ++i )
                re_free(re[i]);

        return 0;
}

#endif
